package leetcode.链表;

/**
 * 反转链表
 */
public class Test206反转链表 {


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    // 方法一：使用栈将原链表压入，然后 pop
    // 实现略



    /**
     * 方法二：原地反转，直接修改原始链表的指针反向指向
     * 所以需要三个辅助变量：保存前一个指针的 pre、处理当前元素的指针 cur、即将要处理的 next
     * 1. 先将 cur.next 指向 pre 即完成了 cur节点指向的反转
     * 2. 将 pre 指向当前的 cur，完成 pre 的向前移动
     * 3. 将 cur 指向 next，完成 cur 的向前移动
     * 4. 若 cur 不为 null，则 next = cur.next 完成 next 的向前移动
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next; // 将这一步放到循环体里面有两个作用
            // 1. 防止 null 指针报错，若 cur 为 null 的话，就取不到他的 next
            // 2. 让指针往下走
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        l1.next = l2;
        l2.next = l3;
       ListNode pre =  reverseList(l1);
        while (pre != null) {
            System.out.print(pre.val);
            pre = pre.next;
        }
    }
}
